首先预处理出一个人能介绍的人的集合 。（包括他本身）
令 表示让集合 中的人相互认识最少需要几个人。
那么可以刷表转移：
边界条件 。
可以看出，第一问的答案为全集的 dp 值。
第二问记录前驱状态和转移到当前状态用的人即可。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 22;
int n , m , rel[ MAXN + 5 ];
int dp[ 1 << MAXN ] , pre[ 1 << MAXN ] , prei[ 1 << MAXN ];
int main( ) {
scanf("%d %d",&n,&m);
if( m == n * ( n - 1 ) / 2 ) return printf("0") & 0;
for( int i = 1 , u , v ; i <= m ; i ++ ) {
scanf("%d %d",&u,&v); u -- , v --;
rel[ u ] |= 1 << v; rel[ v ] |= 1 << u;
}
for( int i = 0 ; i < n ; i ++ ) rel[ i ] |= 1 << i;
memset( dp , 0x3f , sizeof( dp ) );
for( int i = 0 ; i < n ; i ++ ) dp[ rel[ i ] ] = 1 , prei[ rel[ i ] ] = i;
for( int S = 0 ; S < 1 << n ; S ++ )
for( int i = 0 ; i < n ; i ++ )
if( S & ( 1 << i ) && dp[ S | rel[ i ] ] > dp[ S ] + 1 ) {
dp[ S | rel[ i ] ] = dp[ S ] + 1;
pre[ S | rel[ i ] ] = S; prei[ S | rel[ i ] ] = i;
}
printf("%d\n", dp[ ( 1 << n ) - 1 ] );
for( int i = ( 1 << n ) - 1 ; i ; i = pre[ i ] ) printf("%d " , prei[ i ] + 1 );
return 0;
}
